AlgorithmsBasic Concepts

Algorithms(알고리즘)

알고리즘

Definition

Applying a technique to a problem results in a step-by-step procedure for solving the problem. This step-by-step procedure is called an algorithm for the problem.

알고리즘이란 문제를 해결하기 위한 일련의 절차적인 과정이다.


Objectives

The purpose of studying these techniques and their applications is so that, when confronted with a new problem, you have a repertoire of techniques to consider as possible ways to solve the problem.

알고리즘을 학습하는 목적은 새로운 문제에 직면했을 때, 그 문제를 해결할 수 있는 방법으로 고려해야 할 기술의 레퍼토리를 가지기 위함이다.

In addition, we will be concerned not only with determining whether a problem can be solved using a given technique but also with analyzing how efficient the resulting algorithm is in terms of time and storage.

주어진 기술을 사용하여 문제해결의 가능여부를 결정해야 하며, 알고리즘의 결과가 시간 및 스토리지면에서 얼마나 효율적인지 분석해야 한다.


The Importance of Developing Efficient Algorithms

Regardless of how fast computers become or how cheap memory gets, efficiency will remain an important consideration. Next we show why this is so by comparing two algorithms for the same problem.

컴퓨터가 얼마나 빨라지거나 메모리가 얼마나 저렴한지에 관계없이 알고리즘의 효율성은 여전히 ​​중요한 고려사항이다.

Array Size Number of Comparisons
by Sequential Search		 Number of Comparisons
by Binary Search
128 128 8
1,024 1,024 11
1,048,576 1,048,576 21
4,294,967,296 4,294,967,296 33

Binary Search does only 33 comparisons, whereas Sequential Search compares x with all 4 billion items. Even if the computer was capable of completing one pass through the while loop in a nanosecond, Sequential Search would take 4 seconds to determination almost instantaneously. This difference would be significant in an online application or if we needed to search for many items.

Binary Search는 33번의 비교연산이면 충분하지만, Sequential Search는 40억개의 배열항목과 모두 비교해야 한다. 이 차이는 온라인 응용프로그램이나 많은 항목을 검색해야 할 때 중대한 사항이다.


The Important Features of Algorithms

Input(입력)

  • Information or data that comes in.

Output(출력)

  • Information or data that goes out.

Definiteness(명확성)

  • Precisely defined.
    각 단계는 명확하게 정의되어야 한다.

Correctness(정확성)

  • Outputs correctly relate to inputs.
    입력 값의 각 집합에 대해서 정확한 출력 값을 만들어야 한다.

Finiteness(유한성)

  • Won’t take forever to describe or run.

Effectiveness(효율성)

  • Individual steps are all do-able.
    각 단계는 유한한 양의 시간에 수행되어야 한다.

Generality(일반성)

  • Works for many possible inputs.
    특정한 입력이 아닌 모든 가능한 입력에 대해서 동작하여야 한다.
Share